//给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。 
//
// 如果数组中不存在目标值 target，返回 [-1, -1]。 
//
// 你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [5,7,7,8,8,10], target = 8
//输出：[3,4] 
//
// 示例 2： 
//
// 
//输入：nums = [5,7,7,8,8,10], target = 6
//输出：[-1,-1] 
//
// 示例 3： 
//
// 
//输入：nums = [], target = 0
//输出：[-1,-1] 
//
// 
//
// 提示： 
//
// 
// 0 <= nums.length <= 10⁵ 
// -10⁹ <= nums[i] <= 10⁹ 
// nums 是一个非递减数组 
// -10⁹ <= target <= 10⁹ 
// 
//
// Related Topics 数组 二分查找 👍 2307 👎 0

//leetcode submit region begin(Prohibit modification and deletion)


class Solution34 {
    public int[] searchRange(int[] nums, int target) {
        int smallIx = searchAbout(nums, target, true);
        int bigIx = searchAbout(nums, target, false);
        if (smallIx < bigIx && bigIx - 1 < nums.length && bigIx > 0 && nums[bigIx - 1] == target) {
            return new int[]{smallIx + 1, bigIx - 1};
        }

        return new int[]{-1, -1};
    }

    // 查找靠近 target 的, less or more
    int searchAbout(int[] nums, int about, boolean less) {
        int smallIx = -1;
        int bigIx = nums.length;
        int l = 0, r = nums.length - 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (nums[mid] == about) {
                if (less) {
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            } else if (nums[mid] < about) {
                if (less) {
                    smallIx = mid; // 可能的答案, 先记下来
                }
                l = mid + 1;
            } else {
                if (!less) {
                    bigIx = mid;
                }
                r = mid - 1;
            }
        }

        return less ? smallIx : bigIx;
    }

}
//leetcode submit region end(Prohibit modification and deletion)

class Test34 {
    public static void main(String[] args) {
        // int[] nums = {5, 7, 7, 8, 8, 10};
        int[] nums = {1};
        int target = 1;
        // int[] res = new Solution().searchRange(nums, target);
        // Sout.println(res);
    }
}